package com.example.demo.leetcode.zuocheng.btree;

import java.util.Stack;

import com.example.demo.leetcode.jianzhi.Btree_树的子结构;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/8/28 13:18
 */
public class Tree_先序_中序_后序_非递归 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    // 先序遍历 非递归
    public static void first_order(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){

            TreeNode pop = stack.pop();
            System.out.println("遍历:"+pop.val);
            if(pop.right != null){
                stack.push(pop.right);
            }
            if(pop.left!=null){
                stack.push(pop.left);
            }
        }
    }

    //中序遍历 非递归
    // 先递归左边的
    // 左边递归到底部为空，弹出父节点打印，指向右边
    public static void center_order(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();
        TreeNode head = root;

        while(!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head=head.left;
            }else{
                head = stack.pop();
                System.out.println("遍历:"+head.val);
                head = head.right;

            }
        }
    }


    //后序遍历 非递归
    //利用两个栈
    public static void last_order(TreeNode root){

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);

        while(!s1.isEmpty()){
            TreeNode pop = s1.pop();
            s2.push(pop);
            if(pop.left!=null){
                s1.push(pop.left);
            }
            if(pop.right!=null){
                s1.push(pop.right);
            }

        }

        while(!s2.isEmpty()){
            System.out.println("遍历:"+s2.pop().val);
        }
    }










    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.left=treeNode2;treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;treeNode3.right=treeNode7;

        last_order(treeNode1);
    }

}
